package algorithm.leetcode.I1001to1200;

public class Q1024 {
    public int videoStitching(int[][] clips, int T) {
        if (T == 0) {
            return 0;
        }

        int[] dp = new int[T+1];
        dp[0] = 0;

        for (int i = 1; i < dp.length; i++) {
            dp[i] = clips.length+1;
            for (int j = 0; j < clips.length; j++) {
                if (clips[j][0] <= i && clips[j][1] >= i) {
                    dp[i] = Math.min(dp[i], dp[clips[j][0]]+1);
                }
            }
        }
        return dp[T] == clips.length+1 ? -1 : dp[T];
    }

    public static void main(String[] args) {
        Q1024 oztf = new Q1024();
        int[][] clips = {{0,1},{6,8},{0,2},{5,6},{0,4},{0,3},{6,7},{1,3},{4,7},{1,4},{2,5},{2,6},{3,4},{4,5},{5,7},{6,9}};
//        int[][] clips = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
        int T = 10;
        int res = oztf.videoStitching(clips, T);
        System.out.println(res);
    }
}
